Sum of nodes with even-valued grandparent

Time: O(N); Space: O(H); medium

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output: 18

Explanation:

  • The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:

  • The number of nodes in the tree is between 1 and 10^4.

  • The value of nodes is between 1 and 100.

Hints:

  1. Traverse the tree keeping the parent and the grandparent.

  2. If the grandparent of the current node is even-valued, add the value of this node to the answer.

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def sumEvenGrandparent(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def sumEvenGrandparentHelper(root, p, gp):
            return sumEvenGrandparentHelper(root.left, root.val, p) + \
                   sumEvenGrandparentHelper(root.right, root.val, p) + \
                   (root.val if gp is not None and gp % 2 == 0 else 0) \
                   if root else 0
        return sumEvenGrandparentHelper(root, None, None)

[4]:

s = Solution1()

root = TreeNode(6)
root.left, root.right = TreeNode(7), TreeNode(8)
root.left.left, root.left.right = TreeNode(2), TreeNode(7)
root.right.left, root.right.right = TreeNode(1), TreeNode(3)
root.left.left.left = TreeNode(9)
root.left.right.left, root.left.right.right = TreeNode(1), TreeNode(4)
root.right.right.right = TreeNode(5)
assert s.sumEvenGrandparent(root) == 18